#include<iostream>
#include<vector>

using namespace std;

int main(){
	int n, k, m;
	cin>>n>>k>>m;
	vector<vector<int>> relation(m, vector<int>(2));
	for(int i=0;i<m;i++){
		cin>>relation[i][0]>>relation[i][1];
	}

	vector<int> dp(n);
    dp[0] = 1;
    for (int i = 0; i < k; i++) {
        vector<int> next(n);
        for (auto& edge : relation) {
            int src = edge[0], dst = edge[1];
            next[dst] += dp[src];
        }
        dp = next;
    }
    cout<<dp[n - 1]<<endl;
    return 0;
} 
